[1]:
%run ../initscript.py
HTML("""
<div id="popup" style="padding-bottom:5px; display:none;">
<div>Enter Password:</div>
<input id="password" type="password"/>
<button onclick="done()" style="border-radius: 12px;">Submit</button>
</div>
<button onclick="unlock()" style="border-radius: 12px;">Unclock</button>
<a href="#" onclick="code_toggle(this); return false;">show code</a>
""")
[1]:
[2]:
%run ./loadoptfuncs.py
%matplotlib inline
toggle()
[2]:
Linear Programming¶
All optimization models have several common elements:
Decision variables the variable whose values the decision maker is allowed to choose. The values of these variables determine such outputs as total cost, revenue, and profit.
An objective function (objective, for short) to be optimized – minimized or maximized.
Constraints that must be satisfied. They are usually physical, logical, or economic restrictions, depending on the nature of the problem.
In searching for the values of the decision variables that optimize the objective, only those values that satisfy all of the constraints are allowed.
To optimize means that you must systematically choose the values of the decision variables that make the objective as large (for maximization) or small (for minimization) as possible and cause all of the constraints to be satisfied.
Any set of values of the decision variables that satisfies all of the constraints is called a feasible solution. The set of all feasible solutions is called the feasible region.
As one of the fundamental prescriptive analysis method, linear programming (LP) is used in all types of organizations, often on a daily basis, to solve a wide variety of problems. More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and/or linear inequality constraints.
A PC manufacturer assembles and then tests two models of computers, Basic and XP. There are at most 10,000 assembly hours at the cost of $11 available and 3000 testing hours at the cost of $15 available.
data ds_labor;
input type $ cost avail;
datalines;
assemble 11 10000
test 15 3000
;
run;
For each model, it has required assembly, testing hours, cost, price and estimated maximal sales.
data ds_model;
input model $ assemble test cost price max_sale;
datalines;
Basic 5 1 150 300 600
XP 6 2 225 450 1200
;
run;
Business assumptions: - No computers are in inventory from the previous period (or no beginning inventory) - Because these models are going to be changed after this month, the company doesn’t want to hold any inventory after this period (no ending inventory)
Business goal: the PC manufacturer wants to know - how many of each model it should produce - maximize its net profit
Business constraints: - resource constraints: available assembly and testing hours - market constraints: maximal sales
Modeling¶
The PC manufacturer wants to
\begin{align*} \text{maximize} \quad \text{Profit} &= \text{Basic's unit margin} \times \text{Production of Basic} \\ & \qquad \qquad+ \text{XP's unit margin} \times \text{Production of XP} \end{align*}
subject to following constraints: \begin{align*} &\text{assembly hours:} & 5 \times \text{Production of Basic} + 6 \times \text{Production of XP} &\le 10000 \\ &\text{testing hours:} & \text{Production of Basic} + 2\times \text{Production of XP} &\le 3000 \\ &\text{maximal sales:} & \text{Production of Basic} &\le 600 \\ &\text{maximal sales:} & \text{Production of XP} &\le 1200 \\ \end{align*}
Intuitive constraints: \begin{align*} \text{Production of Basic} &\ge 0 \\ \text{Production of XP} &\ge 0 \\ \end{align*}
Graphical solution¶
[3]:
interact(prodmix_graph,
zoom=widgets.Checkbox(value=False, description='Zoom In', disabled=False));
[4]:
interact(prodmix_obj,
zoom=widgets.Checkbox(value=False, description='Zoom In', disabled=False),
margin1=widgets.IntSlider(min=-30,max=150,step=10,value=80,description='Margin Basic:',
style = {'description_width': 'initial'}),
margin2=widgets.IntSlider(min=-30,max=150,step=10,value=129,description='Margin XP:',
style = {'description_width': 'initial'}));
Sensitivity Analysis¶
The sensitivity report from excel shows
Variable Cells
Cell |
Name |
Final Value |
Reduced Cost |
Objective Coefficient |
Allowable Increase |
Allowable Decrease |
|---|---|---|---|---|---|---|
$B$16 |
Number to produce Basic |
560 |
0 |
80 |
27.5 |
80 |
$C$16 |
Number to produce XP |
1200 |
33 |
129 |
1E+30 |
33 |
Final Value: the optimal solution
Reduced Cost: it is relevant only if the final value is equal to either 0 or its upper bound. It indicates how much the objective coefficient of a decision variable (which is currently 0 or at its upper bound) must change before that variable changes. For example:
the number of XPs will stay at 1200 unless the profit margin for XPs decreases by at least $33
Allowable Increase/Decrease: it indicates how much the objective coefficient could change before the optimal solution would change. For example:
if the selling price of Basics stays within a range from $220 to $327.5, the optimal product mix does not change at all.
Constraints
Cell |
Name |
Final Value |
Shadow Price |
Constraint R.H. Side |
Allowable Increase |
Allowable Decrease |
|---|---|---|---|---|---|---|
$B$21 |
Labor availability for assembling Hours used |
10000 |
16 |
10000 |
200 |
2800 |
$B$22 |
Labor availability for testing Hours used |
2960 |
0 |
3000 |
1E+30 |
40 |
Final Value: the value of the left side of the constraint at the optimal solution
Shadow Price: it indicates the change in the optimal value of the objective when the right side of some constraint changes by one unit. For example:
If the right side of this constraint increases by one hour, from 10000 to 10001, the optimal value of the objective will increase by $16.
SAS On Demand¶
Go to the link and click “Not registered or cannot sign in?”
Click “Don’t have a SAS Profile?”
Register a SAS account and login
Select enrollment tab and click “+ enroll in a course”
The course code is: d66f5458-24ac-44b3-8733-13f3ec9f3822
SAS proc optmodel¶
proc optmodel;
/*read in data to set and arrays */
set<str> LABORS;
num cost{LABORS}, avail{LABORS};
read data ds_labor into LABORS=[type] cost avail;
set<str> MODELS;
num price{MODELS}, hours{MODELS,LABORS}, mdl_cost{MODELS}, max_sale{MODELS};
read data ds_model into MODELS=[model] {l in LABORS}<hours[model,l]=col(l)> mdl_cost=cost price max_sale;
num margin{i in MODELS}
= price[i] - mdl_cost[i] - sum{l in LABORS} cost[l] * hours[i,l];
/* *** build model *** */
var Produce{i in MODELS} >=0;
con Maximal_Sales{i in MODELS}:
Produce[i] <= max_sale[i];
con Avail_Labor{l in LABORS}:
sum{i in MODELS} hours[i,l]*Produce[i] <= avail[l];
max Profit=sum{i in MODELS} margin[i] * Produce[i];
solve;
create data solution from [i]=MODELS Produce[i];
quit;
Comparing to spreadsheet modeling, SAS modeling language allows user to separate modeling and solution reporting from data management.
data ds_labor;
input type $ cost avail;
datalines;
assemble 11 20000
test1 19 5000
test2 17 6000
;
run;
data ds_model;
input model $ assemble test1 test2 cost price max_sale;
datalines;
Model1 4 1.5 2 150 350 1500
Model2 5 2 2.5 225 450 1250
Model3 5 2 2.5 225 460 1250
Model4 5 2 2.5 225 470 1250
Model5 5.5 2.5 3 250 500 1000
Model6 5.5 2.5 3 250 525 1000
Model7 5.5 2.5 3.5 250 530 1000
Model8 6 3 3.5 300 600 800
;
run;
proc optmodel;
/*read in data to set and arrays */
set<str> LABORS;
num cost{LABORS}, avail{LABORS};
read data ds_labor into LABORS=[type] cost avail;
set TESTS = {l in LABORS: find(l,'test')>0};
set<str> MODELS;
num price{MODELS}, hours{MODELS, LABORS}, mdl_cost{MODELS}, max_sale{MODELS};
read data ds_model into MODELS=[model] {l in LABORS}<hours[model,l]=col(l)> mdl_cost=cost price max_sale;
num margin{i in MODELS, t in TESTS}
= price[i] - mdl_cost[i] - sum{l in LABORS: l='assemble' or l=t} cost[l] * hours[i,l];
/* *** build model *** */
var Produce{i in MODELS, t in TESTS} >=0;
con Maximal_Sales{i in MODELS}:
sum{t in TESTS} Produce[i,t] <= max_sale[i];
con Avail_Assemble{l in LABORS: l='assemble'}:
sum{i in MODELS} (hours[i,l]*sum{t in TESTS} Produce[i,t]) <= avail[l];
con Avail_Test{l in LABORS: find(l,'test')>0}:
sum{i in MODELS} hours[i,l]*Produce[i,l] <= avail[l];
max Profit=sum{i in MODELS, t in TESTS} margin[i,t] * Produce[i,t];
solve;
create data solution from [t]=TESTS {m in MODELS}<col(m)=Produce[m,t]>;
quit;